package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 148. 排序链表
 * @date 2025/1/21 13:41
 */
public class E148 {

    /**
     * <h3>方法一：归并排序,时间复杂度O(NlogN),空间复杂度理论常数级O(1)</h3>
     *
     * @param head 头节点
     * @return 排序后的链表头节点
     */
    public ListNode sortList1(ListNode head) {
        // 1. 归并排序递归结束条件
        if (head == null || head.next == null) return head;
        // 2. 找到中间节点
        ListNode p1 = head, p2 = head;
        while (p2.next != null && p2.next.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        ListNode median = p1.next;
        // 3. 断开链表
        p1.next = null;
        // 4. 分别对链表1和链表2进行排序
        ListNode l1 = sortList1(head);
        ListNode l2 = sortList1(median);
        // 5. 合并链表
        return mergeTwoLists(l1, l2);
    }

    /**
     * 合并两个链表
     *
     * @param l1 链表1
     * @param l2 链表2
     * @return 合并后的链表头节点
     */
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode sentinel = new ListNode(-1), p = sentinel;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        p.next = l1 == null ? l2 : l1;
        return sentinel.next;
    }

    /**
     * <h3>方法二：计数排序，时间复杂度O(n),空间复杂度O(N)</h3>
     *
     * @param head 头节点
     * @return 排序后的链表头节点
     */
    public ListNode sortList2(ListNode head) {
        // 1. 找到链表最大值和最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        ListNode curr = head;
        while (curr != null) {
            max = Math.max(max, curr.val);
            min = Math.min(min, curr.val);
            curr = curr.next;
        }
        // 2. 创建计数数组
        int[] count = new int[max - min + 1];
        // 3. 遍历链表，填充计数数组
        curr = head;
        while (curr != null) {
            count[curr.val - min]++;
            curr = curr.next;
        }
        // 4. 遍历计数数组，创建链表
        ListNode sentinel = new ListNode(-1), p = sentinel;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                p.next = new ListNode(i + min);
                p = p.next;
                count[i]--;
            }
        }
        // 5. 返回链表头节点
        return sentinel.next;
    }
}
